<!DOCTYPE html>
<html>
<head>
    <style>
        .graph-container {
            width: 600px;
            height: 400px;
            background: #f0f0f0;
            position: relative;
            border-radius: 8px;
        }
        .node {
            width: 40px;
            height: 40px;
            border-radius: 50%;
            background: #90CAF9;
            position: absolute;
            display: flex;
            align-items: center;
            justify-content: center;
            font-size: 16px;
            color: #333;
            transition: all 0.3s;
            cursor: pointer;
            border: 2px solid #1976D2;
        }
        .edge {
            position: absolute;
            height: 2px;
            background: #1976D2;
            transform-origin: left center;
            transition: all 0.3s;
        }
        .result {
            position: absolute;
            top: 10px;
            right: 10px;
            background: white;
            padding: 10px;
            border-radius: 8px;
            font-family: monospace;
            font-size: 14px;
            box-shadow: 0 2px 4px rgba(0,0,0,0.1);
        }
    </style>
</head>
<body style="margin: 0; display: flex; justify-content: center; align-items: center; height: 100vh; background: #f0f0f0;">
    <div class="graph-container" id="graph">
        <div class="result" id="result">拓扑排序结果：</div>
    </div>
    
    <script>
        // 图的节点数据（有向无环图）
        const nodes = [
            { id: 0, x: 300, y: 50, label: 'A' },
            { id: 1, x: 150, y: 150, label: 'B' },
            { id: 2, x: 450, y: 150, label: 'C' },
            { id: 3, x: 100, y: 250, label: 'D' },
            { id: 4, x: 200, y: 250, label: 'E' },
            { id: 5, x: 400, y: 250, label: 'F' },
            { id: 6, x: 500, y: 250, label: 'G' },
            { id: 7, x: 300, y: 350, label: 'H' }
        ];

        // 图的边数据（有向边）
        const edges = [
            [0, 1], [0, 2],
            [1, 3], [1, 4],
            [2, 5], [2, 6],
            [4, 7], [5, 7]
        ];

        // 创建图的可视化
        function createGraph() {
            const container = document.getElementById('graph');
            
            // 创建边
            edges.forEach(([from, to]) => {
                const edge = document.createElement('div');
                edge.className = 'edge';
                const fromNode = nodes[from];
                const toNode = nodes[to];
                
                const length = Math.sqrt(
                    Math.pow(toNode.x - fromNode.x, 2) + 
                    Math.pow(toNode.y - fromNode.y, 2)
                );
                const angle = Math.atan2(
                    toNode.y - fromNode.y,
                    toNode.x - fromNode.x
                );
                
                edge.style.width = `${length}px`;
                edge.style.left = `${fromNode.x + 20}px`;
                edge.style.top = `${fromNode.y + 20}px`;
                edge.style.transform = `rotate(${angle}rad)`;
                
                container.appendChild(edge);
            });
            
            // 创建节点
            nodes.forEach(node => {
                const div = document.createElement('div');
                div.className = 'node';
                div.textContent = node.label;
                div.style.left = `${node.x}px`;
                div.style.top = `${node.y}px`;
                container.appendChild(div);
            });
        }

        // 更新结果显示
        function updateResult(visited) {
            const result = document.getElementById('result');
            const order = visited.map(i => nodes[i].label).join(' → ');
            result.textContent = '拓扑排序结果：' + order;
        }

        // 拓扑排序算法动画
        async function topologicalSort() {
            const nodeElements = document.querySelectorAll('.node');
            const edgeElements = document.querySelectorAll('.edge');
            
            // 创建邻接表
            const adj = Array(nodes.length).fill().map(() => []);
            edges.forEach(([from, to]) => {
                adj[from].push(to);
            });
            
            // 计算入度
            const inDegree = Array(nodes.length).fill(0);
            edges.forEach(([_, to]) => {
                inDegree[to]++;
            });
            
            // 初始化队列（入度为0的节点）
            const queue = [];
            inDegree.forEach((deg, i) => {
                if (deg === 0) {
                    queue.push(i);
                    nodeElements[i].style.backgroundColor = '#FF4081';
                }
            });
            
            const visited = [];
            
            while (queue.length > 0) {
                const current = queue.shift();
                visited.push(current);
                
                // 更新显示
                nodeElements[current].style.backgroundColor = '#4CAF50';
                updateResult(visited);
                await new Promise(resolve => setTimeout(resolve, 1000));
                
                // 处理相邻节点
                for (const next of adj[current]) {
                    // 高亮当前处理的边
                    const edgeIndex = edges.findIndex(
                        ([from, to]) => from === current && to === next
                    );
                    edgeElements[edgeIndex].style.backgroundColor = '#4CAF50';
                    
                    inDegree[next]--;
                    if (inDegree[next] === 0) {
                        queue.push(next);
                        nodeElements[next].style.backgroundColor = '#FF4081';
                    }
                    
                    await new Promise(resolve => setTimeout(resolve, 500));
                }
            }
        }

        // 初始化图并开始动画
        createGraph();
        setTimeout(topologicalSort, 1000);
        
        // 每15秒重置并重新开始
        setInterval(() => {
            const nodes = document.querySelectorAll('.node');
            const edges = document.querySelectorAll('.edge');
            
            nodes.forEach(node => {
                node.style.backgroundColor = '#90CAF9';
            });
            
            edges.forEach(edge => {
                edge.style.backgroundColor = '#1976D2';
            });
            
            document.getElementById('result').textContent = '拓扑排序结果：';
            setTimeout(topologicalSort, 1000);
        }, 15000);
    </script>
</body>
</html> 